package com.ljc;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author ljchen
 * @date 2022-08-08 17:20
 * @desc
 * Write a function to find the longest common prefix string amongst an array of strings.
 *
 * If there is no common prefix, return an empty string "".
 *
 * Example 1:
 * Input: strs = ["flower","flow","flight"]
 * Output: "fl"
 *
 * Example 2:
 * Input: strs = ["dog","racecar","car"]
 * Output: ""
 * Explanation: There is no common prefix among the input strings.
 */
public class E14LongestCommonPrefix {

    public static void main(String[] args) {
        List<String> strList = new ArrayList<String>(){{
            add("flower");
            add("flow");
            add("flight");
        }};

        System.out.println("1: " + findLongestCommonPrefix(strList));

        String[] strs = new String[]{"dog","racecar","car"};
        System.out.println("2: " + findLongestCommonPrefix(strs));

    }

    /**
     * 纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，
     * 如果相同则继续对下一列进行比较，
     * 如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
     * @param strList
     * @return
     */
    public static String findLongestCommonPrefix(List<String> strList) {

        if( strList == null || strList.size() == 0) {
            return "";
        }

        //按照字符串长度有短到长排序
        strList = strList.stream().sorted(Comparator.comparing(String::length)).collect(Collectors.toList());
        System.out.println("sorted: " + strList.toString());

        //获取最短的字符串作为参考
        String shorStr = strList.get(0);
        int shorLength = shorStr.length();
        for (int i = 0; i < shorLength; i++) {
            char a = shorStr.charAt(i);
            for (int j = 1; j < strList.size(); j++) {
                //依次判断数组中每个字符串的每一列是否与参考的字符串相同，若有任何一列不相同 则当前列之前的字符串即为最长前缀
                if (strList.get(j).charAt(i) != a) {
                    return shorStr.substring(0, i);
                }
            }
        }
        return shorStr;

    }

    public static String findLongestCommonPrefix(String[] strs) {

        if( strs == null || strs.length == 0) {
            return "";
        }

        //获取最短的字符串作为参考
        String shorStr = strs[0];
        int shorLength = shorStr.length();
        for (int i = 0; i < shorLength; i++) {
            char a = shorStr.charAt(i);
            for (int j = 1; j < strs.length; j++) {
                //依次判断数组中每个字符串的每一列是否与参考的字符串相同，若有任何一列不相同 则当前列之前的字符串即为最长前缀
                if (strs[j].charAt(i) != a || i == strs[j].length()) {
                    return shorStr.substring(0, i);
                }
            }
        }
        return shorStr;

    }


    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

}
